public class Solution2 {
    public boolean[][] visit;
    public int m;
    public int n;
    public int[] dx = {0, 0, 1, -1};
    public int[] dy = {1, -1, 0, 0};
    public int max;

    public int getMaximumGold(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visit = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] != 0) {
                    visit[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);

                    visit[i][j] = false;
                }
            }
        }

        return max;
    }

    public void dfs(int[][] grid, int i, int j, int sum) {
        if(sum > max) {
            max = sum;
        }
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >=0 && y < n && visit[x][y] == false && grid[x][y] != 0) {
                visit[x][y] = true;
                dfs(grid, x, y, sum + grid[x][y]);
                visit[x][y] =false;
            }
        }
    }
}